/*
 * @Author: your name
 * @Date: 2021-09-22 21:21:40
 * @LastEditTime: 2021-10-03 16:17:12
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \数据结构\树\main.c
 */
#include<stdio.h>
#include<stdlib.h>

//树存储数据类型
typedef int ElemType;
//定义结束数字 
#define END_LEAF_VALUE -1

//节点
typedef struct node
{
    ElemType data;
    struct node* left;
    struct node* right;
}TNode;

/*****************简单栈实现*******************/
typedef struct stack{
    int capacity; //容量
    int top;
    TNode** array; //存储TNode*
}stack;

//创建栈
stack* createStack(int capacity);
//入栈
void push(stack* s,TNode* value);
//出栈
TNode* pop(stack* s);
//判空
int stackEmpty(stack* s);
/*****************简单栈实现*******************/




//创建二叉树
TNode* createTree();
//前序打印
void preorder(TNode* t);
//非递归前序打印
void preorder2(TNode* t);


int main(){
    TNode* t = createTree();
    //前序遍历
    preorder(t);
    //非递归前序
    printf("***********\n");
    preorder2(t);
    return 0;
}

stack* createStack(int capacity)
{
    //栈空间
    stack* s = (stack*)malloc(sizeof(stack));
    if(!s){
        printf("no memory\n");
        return NULL;
    }
    //array
    s->array = (TNode**)malloc(sizeof(TNode*)*(capacity+2));
    if(!s->array){
        printf("no memory\n");
        //释放s
        free(s);
        return NULL;
    }
    //初始化
    s->top = 0;
    s->capacity = capacity;
}

void push(stack* s,TNode* value)
{
    //简化 不做s为空处理和s栈满处理
    s->array[s->top++] = value;
}

TNode* pop(stack* s)
{
    //简化 s为NULL及栈空的情况
    return s->array[--s->top];
}

int stackEmpty(stack* s)
{
    //栈空
    if(s->top == 0){
        return 1;
    }
    return 0;
}

TNode* createTree()
{
    //输入当前节点value
    int value;
    scanf("%d",&value);

    //分支结束
    if(value == END_LEAF_VALUE){
        return NULL;
    }else{
        //创建当前节点并赋值
        TNode* tnode = (TNode*)malloc(sizeof(TNode));
        tnode->data = value;
        //左右分支递归创建
        tnode->left = createTree();
        tnode->right = createTree();
    }
}

void preorder(TNode* t)
{
    if(t){
        printf("%d\n",t->data);
        preorder(t->left);
        preorder(t->right);
    }
}

void preorder2(TNode* t)
{
    //创栈
    stack* s = createStack(10); //这里数据后期可以改成树节点数函数
    TNode* root = t;
    //遍历
    while (root || !stackEmpty(s)){
        //左子入栈
        while(root){
            printf("%d\n",root->data);
            push(s,root);
            root = root->left;
        }
        //左子完 栈出
        if(!stackEmpty(s)){
            root = pop(s)->right;
        }
    }
    
}